computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, the potato peeling or convex skull problem is a problem of finding the

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...

of the largest possible area that lies within a given non-convex

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

. It was posed independently by Goodman and Woo, and solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

by Chang and Yap. The exponent of the polynomial time bound is high, but the same problem can also be accurately approximated in near-linear time.

References

{{reflist, refs= {{citation , last1 = Cabello , first1 = Sergio , last2 = Cibulka , first2 = Josef , last3 = Kynčl , first3 = Jan , last4 = Saumell , first4 = Maria , last5 = Valtr , first5 = Pavel , doi = 10.1137/16M1079695 , issue = 5 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...

, mr = 3708542 , pages = 1574–1602 , title = Peeling potatoes near-optimally in near-linear time , volume = 46 , year = 2017, arxiv = 1406.1368 {{citation , last1 = Chang , first1 = J. S. , last2 = Yap , first2 = C.-K. , doi = 10.1007/BF02187692 , issue = 2 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geom ...

, mr = 834056 , pages = 155–182 , title = A polynomial solution for the potato-peeling problem , volume = 1 , year = 1986, doi-access = free {{citation , last = Goodman , first = Jacob E. , authorlink = Jacob E. Goodman , doi = 10.1007/BF00183192 , issue = 1 , journal =

Geometriae Dedicata ''Geometriae Dedicata'' is a mathematical journal, founded in 1972, concentrating on geometry and its relationship to topology, group theory and the theory of dynamical systems. It was created on the initiative of Hans Freudenthal in Utrecht, the N ...

, mr = 608164 , pages = 99–106 , title = On the largest convex polygon contained in a nonconvex {{mvar, n-gon, or how to peel a potato , volume = 11 , year = 1981 {{citation , last1 = Hall-Holt , first1 = Olaf , last2 = Katz , first2 = Matthew J. , last3 = Kumar , first3 = Piyush , last4 = Mitchell , first4 = Joseph S. B. , author4-link = Joseph S. B. Mitchell , last5 = Sityon , first5 = Arik , contribution = Finding large sticks and potatoes in polygons , doi = 10.1145/1109557.1109610 , mr = 2368844 , pages = 474–483 , publisher = ACM , location = New York , title = Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms , year = 2006, isbn = 978-0898716054 , citeseerx = 10.1.1.59.6770 {{citation, title=The convex skull problem, last=Woo, first=T., year=1983, as cited by {{harvtxt, Chang, Yap, 1986 Convex hulls Computational geometry